package offer;

/**
 * <p>
 * 剑指 Offer 14- I. 剪绳子
 * </p>
 *
 * @author xiaoboom
 * @date 2021/9/24 23:25
 */
public class Offer14 {
    public static void main(String[] args) {
        System.out.println(new Offer14().cuttingRope(120));
    }

    public int cuttingRope(int n) {
        if (n <= 3) {
            return n - 1;
        }
        int b = n % 3;
        int p = 1000000007;
        long rem = 1, x = 3;
        for (int a = n / 3 - 1; a > 0; a /= 2) {
            if (a % 2 == 1) {
                rem = (rem * x) % p;
            }
            x = (x * x) % p;
        }
        if (b == 0) {
            return (int) (rem * 3 % p);
        } else if (b == 1) {
            return (int) (rem * 4 % p);
        } else {
            return (int) (rem * 6 % p);
        }
    }
}
